//Sat 27 Feb 2010 04:42:32 PM CST 
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class SteeplechaseTrack
{
public:
	int maxComplexity(vector <string> fen, vector <string> tra, int n)
	{
		fences = fen;
		tracks = tra;
		N = n;
		int M = fences.size() + 2;
//		int sum = 0;
//		for(int i=0; i<fences.size(); i++)
//		{
//			sum += (fences[i][1]=='0'? 0 : 1);
//		}
//		if(sum == 0) return -1;
//		sum = 0;
//		for(int i=0; i<fences.size(); i++)
//		{
//			sum += (fences[i][2]=='0'? 0 : 1);
//		}
//		if(sum == 0) return -1;
		
		vector<int> weight(M);
		vector<vector<int> > v(M, vector<int>(M, -1));
		
		weight[0] = 0;
		weight[M-1] = 0;
		for(int i=1; i+1<M; i++)
			weight[i] = fences[i-1][0] - '0';
		for(int i=1; i+1<M; i++)
		{
			v[0][i] = (fences[i-1][1]=='0') ? -1 : (fences[i-1][1]-'0');
			v[i][M-1] = (fences[i-1][2]=='0') ? -1 : (fences[i-1][2]-'0');
		}
		
		for(int i=0; i<M-2; i++)
		{
			for(int j=0; j<M-2; j++)
			{
				v[i+1][j+1] = (tracks[i][j]=='0') ? -1 : (tracks[i][j]-'0');
			}
		}
		
		vector<int> count1 = v[0];
		vector<int> count2 = v[0];
		while(N>0)
		{
			for(int i=0; i<M; i++)
			{
				for(int j=0; j<M; j++)
				{
					if(count1[j]>0 && v[j][i]>0)
						count2[i] = max(count2[i], count1[j]+weight[j]+v[j][i]);
				}
			}
			count1 = count2;
			N--;
		}
		return count1[M-1];
	}
	vector<string> fences;
	vector<string> tracks;
	int N;
	int M;
};
